package com.example.algorithm.array;

import java.util.HashMap;

// 本案例演示的是：找出数组中和为S的一对组合，找出一组就行
// 这个就是比较典型的借助双层循环来实现的。只是说内层循环借助的hashMap的containsKey来做的而已。
public class FindSumMatch {
    public static void main(String[] args) {
        int[] arr = {2, 4, 5, 1};
        int[] rst = twoSum(arr, 5);
        System.out.println("The res is: ");
        printArray(rst);

        int[] rst1 = twoSum(arr, 9);
        System.out.println("The res1 is: ");
        printArray(rst1);
    }

    public static int[] twoSum(int[] arr, int s) {// s是那个要求的和
        // map是用来辅助比较的.主要是用containsKey()这个方法。
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        // rst是用来装满足条件的那对组合的，因为我们要找的是是两个元素，所以这里可以固定长度是2。
        int[] rst = new int[2];

        // 先装下数组头部的第一个元素。算是初始化map吧。数的值为键名，索引为值。这一点很重要，因为只有这样，待会才好使用containsKey()这个方法。
        map.put(arr[0], 0); // (2, 0)

        for (int i = 1; i < arr.length; i++) {
            // 如果满足map.containsKey(s - arr[i])，表示配成对了。
            // 其实，这相当于也是一个双层循环的结构，只是我们没有用循环来遍历map，而是用来map自带的containsKey()方法，此方法其实也类似遍历。
            if (map.containsKey(s - arr[i])) {
                // 配成对的这两个值，一个在map里面，我们就用它的键从map里面取出来
                rst[0] = s - arr[i];
                // 还一个不在map里面，它就是当前循环轮的arr[i]
                rst[1] = arr[i];
                return rst;
            } else {
                // 如果当前循环轮的arr[i]与map里面已有的元素不成对，那么，就加入map。
                map.put(arr[i], i);
            }
        }

        return rst;
    }

    public static void printArray(int[] arr) {
        // 增强型for循环，底层基于迭代器，但是它不仅仅适用于没有索引的那种集合类型的遍历哦。
        // 增强型for循环不一定底层就是基于迭代器的。底层基于什么，取决于它遍历的是什么。
        // 如果是遍历的数组，那么它就是转换为普通的for循环，如果是遍历其他没有索引的结合，它们它就转换为迭代器。
        for (int item : arr) {
            System.out.println(item);
        }

    }
}




